package leetcode.newcoder;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * Created by tiang on 2018/7/27.
 * 题目描述
     牛牛的作业薄上有一个长度为 n 的排列 A，这个排列包含了从1到n的n个数，但是因为一些原因，其中有一些位置（不超过 10 个）看不清了，
     但是牛牛记得这个数列顺序对的数量是 k，顺序对是指满足 i < j 且 A[i] < A[j] 的对数，请帮助牛牛计算出，符合这个要求的合法排列的数目。
 输入描述:
     每个输入包含一个测试用例。每个测试用例的第一行包含两个整数 n 和 k（1 <= n <= 100, 0 <= k <= 1000000000），
     接下来的 1 行，包含 n 个数字表示排列 A，其中等于0的项表示看不清的位置（不超过 10 个）。
 输出描述:
    输出一行表示合法的排列数目。
 示例1
     输入
         5 5
         4 0 0 2 0
    输出
        复制
 2
 */
public class SequenceReduction {
    /**
     * 1. 计算缺失的数字及其位置
     2. 对缺失的数字进行全排列，然后填充到对应位置
     3. 计算填充之后的数组的k值
     * @param args
     */

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(),
                k = scanner.nextInt();
        int[] nums = new int[n];
        for(int i=0;i<n;i++)
            nums[i] = scanner.nextInt();
        System.out.println(legalCount(nums, k));
    }

    private static int legalCount(int[] nums, int k){
        boolean[] used = new boolean[nums.length+1];
        List<Integer> leftNum = new ArrayList<>(),
                leftIndex = new ArrayList<>();
        for(int i=0;i<nums.length;i++){
            if(nums[i]!=0) {
                used[nums[i]] = true;
            }else{
                leftIndex.add(i);
            }
        }

        for(int i=1;i<used.length;i++){
            if(!used[i])
                leftNum.add(i);
        }

        List<List<Integer>> list = getOrder(leftNum);
        int count = 0;
        for(List<Integer> l : list){
            for(int i=0;i<leftIndex.size();i++){
                nums[leftIndex.get(i)] = l.get(i);
            }
            if(calculateCount(nums, k))
                count++;
        }
        return count;
    }

    private static List<List<Integer>> getOrder(List<Integer> nums){
        if(nums.size() == 1){
            List<Integer> temp = new ArrayList<>();
            temp.add(nums.get(0));
            List<List<Integer>> l = new ArrayList<>();
            l.add(temp);
            return l;
        }
        List<List<Integer>> result = new ArrayList<>();
        for(int i=0;i<nums.size();i++){
            int num = nums.get(i);
            nums.remove(i);
            List<List<Integer>> list = getOrder(nums);
            for(List<Integer> l : list){
                l.add(num);
                result.add(l);
            }
            nums.add(i, num);
        }
        return result;
    }

    private static boolean calculateCount(int[] nums, int aim){
        int count = 0;
        for(int i=0;i<nums.length;i++){
            for(int j=0;j<i;j++){
                if(nums[j]!=0 && nums[i]> nums[j]){
                    count++;
                    if(count>aim)
                        return false;
                }

            }
        }
        return count == aim;
    }
}
